//
// Created by Administrator on 2021/11/14.
//
/*广度优先遍历(Breadth-First-Search, BFS)要点:
 * 1.找到与一个顶点相邻的所有顶点
 * 2.标记哪些顶点被访问过
 * 3.需要一个辅助队列
 * */
#define MAX_VERTEX_NUM 100//顶点数目的最大值
#define INFINITY 2147483647//最大的int值//宏定义常量"无穷"

typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型

typedef struct {
    VertexType Vex[MAX_VERTEX_NUM];//顶点
    EdgeType Edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//边的权
    int vexnum;//图的当前顶点数
    int arcnum;//图的当前弧数
} Graph;

bool visited[MAX_VERTEX_NUM]; // 访问标记数组

typedef struct QueueNode {
    VertexType data;
    QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front, *rear;//队列的队头和队尾指针
} Queue;

void visit(int i);

void Enqueue(Queue q, int i);

bool isEmpty(Queue q);

void DeQueue(Queue q, int i);

int FirstNeighbor(Graph g, int i);

int NextNeighbor(Graph g, int i, int w);

/*广度优先遍历*/
void BFS(Graph G, int v) {
    Queue Q;
    //从顶点v出发，广度优先遍历图G
    visit(v);//访问初始顶点V
    visited[v] = true;//对v做已访问标记
    Enqueue(Q, v);//顶点v入队列Q
    while (!isEmpty(Q)) {
        DeQueue(Q, v); //顶点v出队列
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            //检测v所有邻接点
            if (!visited[w]) {
                //w为v的尚未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w] = true;//对w做已访问标记
                Enqueue(Q, w); //顶点w入队列
            }//if
        }//for
    }//while
}

void InitQueue(Queue q);

/* 完整版
 * 对图中的所有子图进行BFS遍历*/
void BFSTraverse(Graph G) {
    //对图G进行广度优先遍历
    Queue Q;
    for (int i = 0; i < G.vexnum; ++i) {
        visited[i] = false;//访问标记数组初始化
    }
    InitQueue(Q);// 初始化辅助队列Q
    for (int i = 0; i < G.vexnum; ++i) {
        //从0号顶点开始遍历
        if (!visited[i]) {
            BFS(G, i);//对每个连通分量调用一次BFS
        }
    }//vi未访问过，从vi开始BFS
}

/*时间开销主要来自：
 * 访问各个顶点
 * 访问各个边*/

/*******************************************************/
void DFS(Graph G, int v) {
    //从顶点v出发，深度优先遍历图G
    visit(v);//访问顶点v
    visited[v] = true;//设已访问标记
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            //w为u的尚未访问的邻接顶点
            DFS(G, w);
        };
    } //if
}

/*DFS*/
void DFSTraverse(Graph G) {
    //对图G进行深度优先遍历
    for (int v = 0; v < G.vexnum; ++v) {
        visited[v] = false;//初始化已访问标记数据
    }
    for (int v = 0; v < G.vexnum; ++v) {
        //本代码中是从v=0开始遍历
        if (!visited[v]) {
            DFS(G, v);
        }
    }
}
/********************************************************************/
/*BFS单源最短路径问题
 * 求顶点u到其他顶点的最短路径*/
void BFS_MIN_Distance(Graph G, int u) {
    Queue Q;
    int d[G.vexnum];//d[i]表示从u到i结点的最短路径
    int path[G.vexnum];
    for (int i = 0; i < G.vexnum; ++i) {
        d[i] = INFINITY;//初始化路径长度
        path[i] = -1; //最短路径从哪个顶点过来
    }
    d[u] = 0;//最开始访问的点
    visited[u] = true;//标记：已访问
    Enqueue(Q, u);//入队
    while (!isEmpty(Q)) {
        //BFS算法主过程
        DeQueue(Q, u);//队头元素u出队
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            if (!visited[w]) {
                //w为u的尚未访问的邻接顶点
                d[w] = d[u] + 1;//路径长度+1
                path[w] = u;//最短路径应从u到w
                visited[w] = true;//标记：已访问
                Enqueue(Q, w);//顶点w入队
            };
        }//if
    }//while
}
